﻿#include <stdio.h>
#include <stdlib.h>

// 生成奇数阶魔方阵（Siamese方法）
void generateOdd(int n, int** arr) {
    int currow = 0;
    int curcol = n / 2;
    arr[currow][curcol] = 1;

    for (int i = 2; i <= n * n; i++) {
        // 计算右上位置
        int nextrow = (currow - 1 + n) % n;
        int nextcol = (curcol + 1) % n;

        if (arr[nextrow][nextcol] != 0) {
            // 右上有值则下移
            currow = (currow + 1) % n;
        }
        else {
            // 否则移至右上
            currow = nextrow;
            curcol = nextcol;
        }
        arr[currow][curcol] = i;
    }
}

// 生成4k型偶数阶魔方阵（对称交换法）
void generate4k(int n, int** arr) {
    // 按顺序填充1~n²
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arr[i][j] = i * n + j + 1;
        }
    }

    // 交换对角线元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 主对角线(i==j)或副对角线(i+j==n-1)
            if (i % n == j % n || i % n + j % n == n - 1) {
                arr[i][j] = n * n - i * n - j;
            }
        }
    }
}

// 生成4k+2型偶数阶魔方阵（改进Strachey方法）
void generate4k2(int n, int** arr) {
    int m = n / 2;  // 子矩阵阶数（奇数）
    int k = m / 2;  // 交换区域大小参数
    int quarter = n * n / 4;  // 四分之一区域的数值偏移

    // 1. 初始化四个子矩阵
    // 左上子矩阵（使用奇数阶方法）
    int** sub = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        sub[i] = (int*)calloc(m, sizeof(int));
    }
    generateOdd(m, sub);

    // 2. 填充四个子矩阵
    // 左上
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            arr[i][j] = sub[i][j];
        }
    }
    // 右下（+1个quarter）
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            arr[i + m][j + m] = sub[i][j] + quarter;
        }
    }
    // 右上（+2个quarter）
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            arr[i][j + m] = sub[i][j] + 2 * quarter;
        }
    }
    // 左下（+3个quarter）
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            arr[i + m][j] = sub[i][j] + 3 * quarter;
        }
    }

    // 3. 区域交换（关键步骤）
    // 交换1：右半部分特定列
    int swapColStart = m + k + 1;  // 交换起始列
    for (int j = swapColStart; j < n; j++) {
        for (int i = 0; i < m; i++) {
            int temp = arr[i][j];
            arr[i][j] = arr[i + m][j];
            arr[i + m][j] = temp;
        }
    }

    // 交换2：中心位置交换
    int center = m / 2;
    int temp = arr[center][center];
    arr[center][center] = arr[center + m][center];
    arr[center + m][center] = temp;

    // 交换3：左半部分特定区域（除中心行第一列）
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            if (i == center && j == 0) continue;  // 跳过中心行第一列
            temp = arr[i][j];
            arr[i][j] = arr[i + m][j];
            arr[i + m][j] = temp;
        }
    }

    // 释放临时子矩阵
    for (int i = 0; i < m; i++) {
        free(sub[i]);
    }
    free(sub);
}

// 打印魔方阵
void printMagicSquare(int n, int** arr) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%-4d", arr[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n;
    printf("请输入魔方阵阶数n(n≥3): ");
    scanf_s("%d", &n);

    if (n < 3) {
        printf("阶数必须大于等于3！\n");
        return 1;
    }

    // 动态分配二维数组
    int** arr = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        arr[i] = (int*)calloc(n, sizeof(int));
    }

    // 根据阶数类型生成魔方阵
    if (n % 2 == 1) {
        // 奇数阶
        generateOdd(n, arr);
    }
    else if (n % 4 == 0) {
        // 4k型偶数阶
        generate4k(n, arr);
    }
    else {
        // 4k+2型偶数阶
        generate4k2(n, arr);
    }

    // 输出结果
    printf("%d阶魔方阵如下：\n", n);
    printMagicSquare(n, arr);

    // 释放内存
    for (int i = 0; i < n; i++) {
        free(arr[i]);
    }
    free(arr);

    return 0;
}
